package com.zk.algorithm.sortingandsearching;

/**
 * 二分查找变形问题 - 极客时间
 *
 * @author zk
 */
public class BinarySearch {

    /**
     * 查找第一个值等于某个值的元素
     *
     * @param a
     * @param n
     * @param value
     * @return
     */
    public int findFirstValue(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] > value) { /** 大于 **/
                high = mid - 1;
            } else if (a[mid] < value) { /** 小于 **/
                low = mid + 1;
            } else { /** 相同 **/
                if ((mid == 0) || (a[mid - 1] != value)) return mid; /** 左边数 != 值，那就是第一个了 **/
                else high = mid - 1; /** high 主动减 1 **/
            }
        }

        return -1;
    }

    /**
     * 查找最后一个值等于给定值的元素
     *
     * @param a
     * @param n
     * @param value
     * @return
     */
    public int findLastValue(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;

        while (low <= high) {
            int mid =  low + ((high - low) >> 1);
            if (a[mid] > value) {
                high = mid - 1;
            } else if (a[mid] < value) {
                low = mid + 1;
            } else {
                if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
                else low = mid + 1;
            }
        }

        return -1;
    }

    /**
     * 查找第一个大于等于给定值的元素
     *
     * @param a
     * @param n
     * @param value
     * @return
     */
    public int findFirstLargeOrEqual(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] >= value) { /** 大于等于 **/
                if ((mid == 0 /** 前面没有元素 **/) ||

                        // 3, 4, 6, 7, 10 查找 5
                        //    ↑
                        //  4 < 5
                        (a[mid - 1] < value /** 前面一个元素小于 value **/)) return mid;
                else high = mid - 1;
            } else { /** 小于 **/
                low = mid + 1;
            }
        }

        return -1;
    }

    /**
     * 查找最后一个小于等于给定值的元素
     *
     * @param a
     * @param n
     * @param value
     * @return
     */
    public int findLastLessOrEqual(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;

        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (a[mid] > value) {
                high = mid - 1;
            } else {
                if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
                else low = mid + 1;
            }
        }

        return -1;
    }

}
